package com.datastructures.recursion;

/**
 * @author MaoLin Wang
 * @date 2019/10/2510:03
 */
public class MiGong {
    public static void main(String[] args) {
        //1.使用二维数组模拟迷宫
        int[][] map = new int[8][7];
        /**
         * 1作为障碍物,最外围的一圈都置为1
         */
        for (int i=0;i<7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }

        //左右全部置为1
        for (int i=0;i<8;i++){
            map[i][0]=1;
            map[i][6]=1;
        }

        //设置挡板
        map[3][1] = 1;
        map[3][2] = 1;
        map[5][3]=1;
        //输出
        for (int i=0;i<8;i++){
            for (int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

        //递归回溯找路
        setWay(map,2,1);
        //输出走过并标识过的地图
        System.out.println("路：");
        for (int i=0;i<8;i++){
            for (int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }



    /**
     * 使用递归回溯来给小球找路
     * 1.如果小球到[6][5]则找到路
     * 2.当map[i][j]为0时，表示该点没有走过，当为1的时候表示障碍物，为2的时候是可以走的通路,3表示已经走过但走不通
     * 3.确定策略： 下-> 右-> 上 -> 左，走不通就回溯
     * @param map 迷宫
     * @param i 从第i,j个位置开始找
     * @param j
     * @return 找到返回true 否则为false
     */
    public static boolean setWay(int[][] map,int i,int j){

        if(map[6][5]==2){//找到通路
            return true;
        }else {
            if(map[i][j] == 0){
                //当前点未走过
                map[i][j]=2; //假定该点可以走通
                if (setWay(map,i+1,j)){//向下走
                    return true;
                }else if (setWay(map,i,j+1)){//向右走
                    return true;
                }else if (setWay(map,i-1,j)){//向上走
                    return true;
                }else if (setWay(map,i,j-1)){//向左走
                    return true;
                }else {
                    //没有通路，置为3
                    map[i][j]=3;
                    return false;
                }
            }else {//可能是 1，2，或3
                return false;
            }
        }

    }
}
